package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/reverse-nodes-in-even-length-groups/description/
 * <p>
 * 2074. 反转偶数长度的链表节点
 * <p>
 * 给你一个链表的头节点 head 。
 * <p>
 * 链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的 长度 就是组中分配到的节点数目。换句话说：
 * <p>
 * 节点 1 分配给第一组
 * 节点 2 和 3 分配给第二组
 * 节点 4、5 和 6 分配给第三组，以此类推
 * 注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
 * <p>
 * 反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。
 *
 * @author hanjuntao
 * @date 2025/8/5 0005
 */
public class L_2074_reverse_nodes_in_even_length_groups {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        ListNode node9 = new ListNode(9);
        ListNode node10 = new ListNode(10);
        ListNode node11 = new ListNode(11);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
//        node5.next = node6;
//        node6.next = node7;
//        node7.next = node8;
//        node8.next = node9;
//        node9.next = node10;
//        node10.next = node11;

        ListNode result = reverseEvenLengthGroups(node1);
        ListNode.print(result);
    }

    /**
     * 思路：
     * <p>
     * 这个题和分组反转链表的思路一样，分组反转链表，是一组固定长度
     * 这一题，仅偶数长度的链表进行反转。
     * <p>
     * 所以我们需要定一个函数，用来获取一次组的长度。
     * <p>
     * 当当前组的长度为偶数，则进行反转
     * <p>
     * 注意：
     * 最后一组可能不够达到下一次组的长度，就按照实际长度为准
     *
     * @param head
     * @return
     */
    public static ListNode reverseEvenLengthGroups(ListNode head) {
        // 当前元素的个数索引
        int index = 0;

        // 当前组的元素个数
        int groupItemCount = 0;
        // 当前组的长度
        int groupLength = 1;

        ListNode curr = head;
        while (curr != null) {
            index++;
            groupItemCount++;

            ListNode next = curr.next;

            // 如果是最后一组，则判断当前组长度是否为偶数
            // 偶数长度
            if (groupItemCount == groupLength || next == null) {
                if (groupItemCount % 2 == 0) {
                    int start = index - groupItemCount + 1;
                    reverseBetween(head, start, index);
                }

                // 获取下一组长度,如果还在组内，返回长度不变
                groupLength = getNextGroupLength(groupLength, groupItemCount);

                groupItemCount = 0;
            }

            curr = next;
        }

        return head;
    }

    private static int getNextGroupLength(int groupLength, int groupItemCount) {
        if (groupItemCount == groupLength) {
            return groupLength + 1;
        }
        return groupLength;
    }


    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) {
            return null;
        }

        if (right < left) {
            return head;
        }

        // 选中链表头结点的上一个节点
        ListNode lastDealHead = null;
        // 选中链表头结点
        ListNode dealHead = null;
        // 选中链表尾结点
        ListNode dealTail = null;
        // 选中链表尾结点下一个节点
        ListNode nextDealTail = null;

        ListNode curr = head;
        int begin = 1;

        while (curr != null) {
            if (begin == left - 1) {
                lastDealHead = curr;
            }

            if (begin == left) {
                dealHead = curr;
            }

            if (begin == right) {
                dealTail = curr;

                // 可能是空
                nextDealTail = curr.next;
            }

            begin++;
            curr = curr.next;
        }

        if (dealTail != null) {
            dealTail.next = null;
        }

        ListNode newHead = revereList(null, dealHead);

        if (lastDealHead == null) {
            dealHead.next = nextDealTail;
            return newHead;
        } else {
            lastDealHead.next = newHead;
            dealHead.next = nextDealTail;
            return head;
        }
    }

    private static ListNode revereList(ListNode prev, ListNode dealHead) {
        if (dealHead == null) {
            return prev;
        }

        ListNode next = dealHead.next;
        dealHead.next = prev;
        return revereList(dealHead, next);
    }

}
